#include <iostream>

using namespace std;

#define N 5

int maze[N][N] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0}};

int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int visited[N][N] = {0};
void printPath(int path[N][N], int length)
{
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length; j++)
        {
            cout << path[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int dfs(int x, int y, int path[N][N])
{
    if (x == N - 1 && y == N - 1)
    {
        path[x][y] = 9;
        printPath(path, N);
        return 1;
    }

    visited[x][y] = 3;
    path[x][y] = 6;

    for (int i = 0; i < 4; i++)
    {
        int newX = x + direction[i][0];
        int newY = y + direction[i][1];

        if (newX >= 0 && newX < N && newY >= 0 && newY < N && maze[newX][newY] == 0 && !visited[newX][newY])
        {
            if (dfs(newX, newY, path))
            {
                return 1;
            }
        }
    }

    path[x][y] = 0;
    return 0;
}

int main()
{
    int path[N][N] = {0};
    if (!dfs(0, 0, path))
    {
        cout << "No path found!" << endl;
    }

    return 0;
}